Let's Build a Simple Database
2019-12に完走
Part 3 - An In-Memory, Append-Only, Single-Table Database
insertをできるようにする
disk書き込みなしでメモリ上に保存
テーブルの構造
SQLiteは高速なlookup, insert, deleteのためにB-Treeを使っているがもっとシンプルにする pageと呼ばれるメモリブロックにrowを保存する
pageを木として扱うのではなくただの配列にする
工夫
pageにはrowを載るだけ載せる
rowはpageに載せるためにcompactにserializeする
pageは必要最低限だけ割り当てる
pageは4096 bytesとする
ほとんどのコンピューターアーキテクチャの仮想メモリシステムで使用されるページと同じサイズ
Databaseの1 pageとOSの 1pageが同じ
分割することなくメモリに出し入れできる
page上限を100にしているのは恣意的
pageを超えてrowを保存することは許容しない
pageをまたぐ場合はメモリアドレスが隣接しないだろうから、read / writeが大変になる
Part 4 - Our First Tests (and Bugs)
RSpecで親近感湧いた
Part 5 - Persistence to Disk
メモリにあるデータを永続化したり、次回のプロセス起動時にメモリに読み込んだりする
pagerという抽象がそれを実現する
ページャにページ番号xを要求すると、ページャはメモリブロックを返す
最初にキャッシュを調べる
キャッシュミスが発生すると、データベースファイルを読み取ることによりデータをディスクからメモリにコピーする
ページャはテーブルごとに存在する実装にする
起動時にconnectionを開く
database fileをopenする
pager, tableのdata structureの初期化
終了時にconnectionを閉じる
メモリ解放
起動時にdatabase file名を受け取る
database fileを覗くと面白い
little endian byte orderでidが保存されていたり
uint32_tなので4 bytes
compileしたマシンがlittle endianだからそうなったのでbig endianのマシンでcompileしたら結果は変わる
その場合はserialize, deserializeの処理も変更する必要があるはず
usernameやemailといった文字列がnullで終了していたり
初期化してないメモリの部分はjunkが詰まっている
もしすべてを初期化したいならserializeのところでmemcpyの代わりにstrncpyを使用する
ここまでで永続化できたが課題はある
.exitcommandで終了しないと変更が失われる
変更してない部分もまとめてdatabase fileに書き込まれる
Part 6 - The Cursor Abstraction
cursorという抽象を扱う
テーブルに対するcursorを作成する
cursorを通してrowへアクセスする
このあと更新や削除なども扱う
cursorを進める
cursor struct
tableへの参照
row_num
end_of_table: テーブルの最後の行を超えているかどうかを知るために使う。insertの時に役立つ
cursorを使うよう書き換えていく
insert
tabel_endのcursorを作成し、そのcursor経由でrowのvalueを取得してserializerに渡す
select
tabel_startのcursorを作成し、そのcursor経由でrowのvalueを取得する
cursor->end_of_table == trueになるまでloopする
Part 7 - Introduction to the B-Tree
B-TreeはSQLiteが使用するデータ構造であり、テーブルとインデックスの両方に用いられている 正確には、indexesにはB-Tree、tablesにはB+ Treeが使われている 木構造がなぜデータベースに使われるのか
特定の値の検索が速い（linear time 線形時間ではなくlogarithmic time 対数時間）
すでに見つかっている値の挿入/削除が速い（木のリバランスが定数時間）
範囲検索が速い（hash mapの苦手なところ）
B-Treeはbinary treeではない
binary treeと異なり、B-Treeのnode（濃い青の箱）は2つ以上の子nodeを持つことができる
各nodeが持てる子をm個とするとき、mをその木の"order"と呼ぶ
木がバランシングされるようにするため、各nodeはm/2 (切り上げ) 個の子を持たなければいけない
例: orderが3の場合、各nodeは最低2個の子nodeを持つ
ただし例外がある
leaf nodes (末端のnode) は子を持たない
root nodeはmより少ない数の子を持てるが、最低でも2つの子を持たなければいけない
ただしroot nodeがlead nodeの場合 (nodeが一つしかない)、0個で良い
今回はこのデータ構造を以下の様に実現する
各nodeが1 pageに対応するようにする
root nodeはpage 0に存在する
子pointerは、子nodeを含むpage numberになる
Indexの実装に着手するまで、このレッスンではB+ TreeのことをbtreeまたはB-Treeと呼んでいく
Part 8 - B-Tree Leaf Node Format
tableの形をunsorted arrayからB-Treeに変更する
なぜB-Treeにするのかもう一度整理
今のformat
空間効率は良い、row情報以外のmetadataをもたない
appendするinsertionは速い O(1)
searchは遅い、フルスキャン（全rowの走査）が起きる O(n)
deletionにおいてarrayのどこかに隙間が生じると、それ以降のrowを全て動かして埋めないといけない O(n)
もしsorted array (by id) だったら？
searchはbinary searchで速くなる O(log(n))
insertionが遅くなる、他のrowを全て動かして埋めないといけない O(n)
deletionは変わらない O(n)
B-Treeにすると
単なるkey, valueだけでなくinternal nodeなどのmetadataを作るので情報量が増える
database fileの肥大化と引き換えに高速な検索/挿入/削除が可能になる (全て O(log(n)))
各nodeが1 pageに対応する
internal nodeは子nodeを保持するpage numberを持つことで子nodeへの参照を持つ
B-Treeはpagerにpage numberを要求する、cacheへのpointerを返すように要求する
pageは、page numberの順にdatabase fileに保存される
Node format
各nodeはmetadataとしてnode headerを持つ
node type
root nodeなのかどうか
親nodeへの参照（隣り合ったnodeを探すため）
Leaf node format
node headerに加え、leaf nodeが持つcells (実際のrow) の情報も持つ
leaf node bodyはcellの配列
各cellはkeyとそれに続くvalue
無駄な部分があるが、key, valueのサイズを確保出来ない部分は放っておく。nodeをまたいでのcellを作らないため
Changes to Pager and Table Objects コードを書き換えていく
nodeとpageが対応するようになってので、pagerに部分的にpageを読んだり書いたりする必要がなくなった
行数ではなくページ数をデータベースに保存する方が理にかなっている
ページ数は、特定のテーブルではなくデータベースで使用されるページ数であるため、テーブルではなくpagerに関連付ける
B-Treeはそのroot nodeのpage numberで識別されるため、table objectはそれを追跡できるようになる
Changes to the Cursor Object
tableが単純なarrayだったときにはrow_numでアクセスできたが、page_num (nodeへの参照) とcell_numが必要になる
Insertion Into a Leaf Node
databse fileをopenしたときにpager->num_pages == 0であればemtyなlead node (かつroot node) を作る
cursor key valueを受け取ってinsertするfunctionを作る
nodeの分割処理を実装していないので、leaf nodeのmax cellsを超えたらエラーになるようにする
課題
leaf nodeに保存するようにはしたもののinsertの時にsorted orderで保存せずにtable_endが返すところにそのままinsertしているので、そこはこれまで通りのまま
保存できる行数が減った
次
primary keyでのsearch
rowsをsorted orderで保存する
Part 9 - Binary Search and Duplicate Keys
node内でbinary searchして挿入すべき箇所を決定するようにする
挿入しようとしているkeyがすでに存在する場合はduplicated errorを返す
Part 10 - Splitting a Leaf Node
nodeをsplitする
新しいpageを作る
全てのcellを新しいnodeに移す
node headerの数をcount upする
nodeのparentを更新する
もしroot nodeだった場合は新たにroot nodeを作成する
2つの新しいノード間でセルを均等に分散する
internal nodeのレイアウトを決める
Part 11 - Recursively Searching the B-Tree
internal nodeをたどって再帰的に検索できるようにする
Part 12 - Scanning a Multi-Level B-Tree
今の実装の問題
15行追加するとselectが壊れる
table_startがroot nodeのcell 0を返すが、node splitするとroot nodeはleaf nodeではなくinternal nodeであり、なんのcellも持たない
table_findでkey = 0を検索すれば開始地点のcursor (the left-most leaf node)を返す
これでも1 leaf nodeしか辿っていないのでselect allにならない
次のleaf nodeを指す情報 next_leaf をleaf node headerに足す
次がなければ0
leaf nodeをsplitするときにnext_leafの情報を更新する
cursorを進める時にleaf nodeのcell数に到達したらend of tableとするのではなく、next_leafをチェックしてあれば次に進む
これでokと思ったらleaf nodeのsplitのところにbugがあり、壊れたデータがある
code:sql
db > select
(1, user1, person1@example.com)
(2, user2, person2@example.com)
(3, user3, person3@example.com)
(4, user4, person4@example.com)
(5, user5, person5@example.com)
(6, user6, person6@example.com)
(7, user7, person7@example.com)
(8, user8, person8@example.com)
(9, user9, person9@example.com)
(10, user10, person10@example.com)
(11, user11, person11@example.com)
(12, user12, person12@example.com)
(13, user13, person13@example.com)
(1919251317, 14, on14@example.com)
(15, user15, person15@example.com)
Executed.
db >
keyがあるべきところにvalueを書き込んでいたので予想外のでかいkeyになっている
Part 13 - Updating Parent Node After a Split
leaf node分割時のroot nodeの処理をいじっていく
---
Part 13が2017-11-26に公開されたのを最後に更新が止まっている…
B-Treeの知識がつくと以下の記事などが読める
